package leecode

func partition131(s string) (result [][]string) {
	path := make([]string, 0, len(s))
	var backtracking func(startIndex int)
	backtracking = func(startIndex int) {
		if startIndex >= len(s) {
			temp := make([]string, len(path))
			copy(temp, path)
			result = append(result, temp)
		}
		for i := startIndex; i < len(s); i++ {
			if isAnagram(s[startIndex : i+1]) {
				//是回文串
				str := s[startIndex : i+1]
				path = append(path, str)
			} else {
				continue
			}
			backtracking(i + 1)
			//回溯
			path = path[:len(path)-1]
		}
	}
	backtracking(0)
	return
}

func isAnagram(s1 string) bool {
	s2 := s1
	s2Arr := []byte(s2)
	//反转字符串 s2
	for i := 0; i < len(s2Arr)/2; i++ {
		s2Arr[i], s2Arr[len(s2)-1-i] = s2Arr[len(s2)-1-i], s2Arr[i]
	}
	s2 = string(s2Arr)
	if s1 == s2 {
		return true
	}
	return false
}
